package recursive.KthGrammar;

import java.util.LinkedList;

/**
 * @Date 2020/03/30
 * @author 王光浩
 * @Thinking 使用迭代方式
 * @Analysis 时间复杂度O（2^n）,空间复杂度O（2^n）
 */
public class MyMethodThree {
	public int kthGrammar(int N, int K) {
		LinkedList<Integer> queue=new LinkedList<Integer>();
		queue.add(0);
		while(--N>0) {
			int size=queue.size();
			for(int i=0;i<size;i++){
				if(queue.poll()==0) {
					queue.add(0);
					queue.add(1);
				}
				else {
					queue.add(1);
					queue.add(0);
				}
			}
		}
		return queue.get(K-1);
	}
}
